#include "tree.h"
#include <cstring>
#include <iostream>
#define MAXSIZE 20
Tree::Tree()
{
    this->m_root=0;
    createTree("A(B(D(,G)),C(E,F))");
}
Tree::~Tree()
{
    if(m_root!=0)
        deleteTree(m_root);
}

void Tree::createTree(const char *str)
{
    if(m_root!=0)
        return;
    int mlen=strlen(str);
    TNode* st[MAXSIZE];
    int top=-1;
    bool mleft=true;
    TNode* tmp;

    for(int i=0;i<mlen;i++)
    {
        switch(str[i])
        {
        case '(':
            st[++top]=tmp;
            mleft=true;
            break;
        case ',':
            mleft=false;
            break;
        case ')':
            top--;
            break;
        default:
            tmp=new TNode();
            tmp->data=str[i];
            if(m_root==0)
            {
                m_root=tmp;
            }
            else
            {
                if(mleft)
                {
                    st[top]->lch=tmp;
                }
                else
                {
                    st[top]->rch=tmp;
                }
            }
        }
    }
}
void Tree::printTree(TNode *root)
{
    if(root!=0)
    {
        std::cout<<root->data;
        if(root->lch!=0 || root->rch!=0)
        {
            std::cout<<'(';
            printTree(root->lch);
            if(root->rch!=0)
            {
                std::cout<<',';
            }
            printTree(root->rch);
            std::cout<<')';
        }
    }
}
void Tree::printTree()
{
    printTree(this->m_root);
}
void Tree::deleteTree(TNode *&root)
{
    if(root!=0)
    {
        deleteTree(root->lch);
        deleteTree(root->rch);
        delete root;
        root=0;
    }
}
TNode* Tree::copyTree(TNode *src)
{
    if(src!=0)
    {
        TNode* root=new TNode;
        root->data=src->data;

        root->lch=copyTree(src->lch);
        root->rch=copyTree(src->rch);
        return root;
    }
    else
        return 0;
}
void Tree::preTree()
{
    if(m_root!=0)
    {
        TNode* st[MAXSIZE];
        int top=-1;

        st[++top]=m_root;
//        std::cout<<m_root->data;

        while(top!=-1)
        {
            TNode* tmp=st[top--];
            std::cout<<tmp->data;
            if(tmp->rch!=0)
            {
                st[++top]=tmp->rch;
            }
            if(tmp->lch!=0)
            {
                st[++top]=tmp->lch;
            }
        }
        std::cout<<std::endl;
    }
}
void Tree::inTree()
{
    if(m_root!=0)
    {
        TNode* tmp=m_root;
        TNode* st[MAXSIZE];
        int top=-1;

        while(tmp!=0 || top!=-1)
        {
            while(tmp!=0)
            {
                st[++top]=tmp;
                tmp=tmp->lch;
            }

            TNode* curN=st[top--];
            std::cout<<curN->data;
            tmp=curN->rch;
        }
        std::cout<<std::endl;
    }
}
void Tree::postTree()
{
    if(m_root!=0)
    {
        TNode* tmp=m_root;
        TNode* st[MAXSIZE];
        int top=-1;

        while(tmp!=0 || top!=-1)
        {
            while(tmp!=0)
            {
                st[++top]=tmp;
                tmp=tmp->lch;
            }
            TNode* preN=0;
            while(top!=-1)
            {
                if(st[top]->rch==preN)
                {
                    preN=st[top--];
                    std::cout<<preN->data;
                }
                else
                {
                    tmp=st[top]->rch;
                    break;
                }
            }
        }
        std::cout<<std::endl;
    }
}
bool Tree::insertBST(TNode *&root, char c)
{
    if(root==0)
    {
        root=new TNode;
        root->data=c;
        return true;
    }
    if(root->data==c)
    {
        return false;
    }
    else if(root->data>c)
    {
        return insertBST(root->lch,c);
    }
    else
    {
        return insertBST(root->rch,c);
    }
}
TNode* Tree::createBST(const char *src)
{
    int mlen=strlen(src);
    TNode* result=0;
    for(int i=0;i<mlen;i++)
    {
        insertBST(result,src[i]);
    }
    return result;
}
TNode* Tree::BST2List(TNode *root)
{
    TNode* st[MAXSIZE];
    int top=-1;

    TNode* nextN=root;
    TNode* mhead=0;
    TNode* lastList=0;
    while(nextN!=0 || top!=-1)
    {
        while(nextN!=0)
        {
            st[++top]=nextN;
            nextN=nextN->lch;
        }
        TNode* curN=st[top--];
        if(lastList==0)
        {
            mhead=lastList=curN;
        }
        else
        {
            nextN=curN->rch;

            lastList->rch=curN;
            curN->lch=lastList;
            lastList=curN;

        }
    }
    return mhead;
}
void Tree::printList(TNode *root)
{
    while(root!=0)
    {
        std::cout<<root->data;
        root=root->rch;
    }
    std::cout<<std::endl;
}
bool Tree::printPath(int n, TNode *root,char st[],int top)
{
    if(root==0)
        return false;
    if(root->lch==0 && root->rch==0)
    {
        if(root->data==n)
        {
            st[++top]=root->data;
            for(int i=0;i<=top;i++)
                std::cout<<st[i]<<' ';
            std::cout<<std::endl;
            return true;
        }
        else
            return false;
    }
    else
    {
        bool res=false;
        if(root->lch!=0)
        {
            st[top+1]=root->data;
           if(printPath(n-root->data,root->lch,st,top+1))
               res=true;
        }
        if(root->rch!=0)
        {
            st[top+1]=root->data;
            if(printPath(n-root->data,root->rch,st,top+1))
                res=true;
        }
        return res;
    }
}
void Tree::printPath(int n, TNode *root)
{
    TNode* st[MAXSIZE];
    int top=-1;
    int num=0;

    if(root!=0)
    {
        TNode* tmpN=root;
        while(tmpN!=0 || top!=-1)
        {
            while(tmpN!=0)
            {
                st[++top]=tmpN;
                num+=tmpN->data;
                tmpN=tmpN->lch;
            }
            if(num==n && st[top]->lch==0 && st[top]->rch==0)
            {
                for(int i=0;i<=top;i++)
                {
                    std::cout<<st[i]->data<<' ';
                }
                std::cout<<std::endl;
            }
            TNode* lastN=0;
            while(top!=-1)
            {
                TNode* curN=st[top];
                if(curN->rch==lastN)
                {
                    //access
                    top--;
                    num-=curN->data;
                    lastN=curN;
                }
                else
                {
                    tmpN=st[top]->rch;
                    break;
                }
            }
        }
    }
}
